//
//  CLBinaryTree.m
//  Charles
//
//  Created by Leo on 2019/6/25.
//  Copyright © 2019 charles. All rights reserved.
//

#import "CLBinaryTree.h"
#import "BlocksKit.h"
// https://www.cnblogs.com/manji/p/4903990.html

/**
 递归和栈的关系，当递归调用时每次调用自己时可以看做是压栈过程，当递归条件满足结束时，递归一级一级的返回时可以看做是出栈的过程。
 */
@implementation TreeNode

@end

@implementation CLBinaryTree

/**
 生成一个节点

 @param nodeName 节点名称
 @return 生成的节点
 */
- (TreeNode *)treeNodeWithName:(NSString *)nodeName {
    TreeNode *leafNode = [[TreeNode alloc]init];
    leafNode.nodeName = nodeName;
    return leafNode;
}

/**
 生成一棵树
 @return 生成的二叉树
 */
- (TreeNode *)makeBinaryTree {
    /**
      0
     /   \
    1     6
   / \      / \
  2   3   7   8
    / \
   4   5
     */
    TreeNode *leafOne = [self treeNodeWithName:@"叶子1"];
    TreeNode *leafTwo = [self treeNodeWithName: @"叶子2"];
    TreeNode *leafThree = [self treeNodeWithName: @"叶子3"];
    TreeNode *leafFour = [self treeNodeWithName: @"叶子4"];
    TreeNode *leafFive = [self treeNodeWithName: @"叶子5"];
    TreeNode *leafSix = [self treeNodeWithName: @"叶子6"];
    TreeNode *leafSeven = [self treeNodeWithName: @"叶子7"];
    TreeNode *leafEight = [self treeNodeWithName: @"叶子8"];
    TreeNode *rootNode =[self treeNodeWithName: @"根节点"];
   
    rootNode.leftLeaf = leafOne;
    rootNode.rightLeaf = leafSix;
    
    leafOne.leftLeaf = leafTwo;
    leafOne.rightLeaf = leafThree;
    
    leafThree.leftLeaf = leafFour;
    leafThree.rightLeaf = leafFive;
    
    leafSix.leftLeaf = leafSeven;
    leafSix.rightLeaf = leafEight;
   
    return rootNode;
}

/**
 先序遍历:DLR 先访问根节点，在先序遍历左子树，再先序遍历右子树

 @param tree 要遍历的树
 */
- (void)preorderTraversal:(TreeNode *)tree {
    if (tree) {
        NSLog(@"%@\n",tree.nodeName);
        [self preorderTraversal:tree.leftLeaf];
        [self preorderTraversal:tree.rightLeaf];
    }
}

/**
 中序遍历:LDR 中序遍历左子树,访问根节点,中序遍历右子树
 访问顺序：左中右

 @param tree 要遍历的树
 */
- (void)inorderTraversal:(TreeNode *)tree {
    if (tree) {
        [self inorderTraversal:tree.leftLeaf];
        NSLog(@"%@\n",tree.nodeName);
        [self inorderTraversal:tree.rightLeaf];
    }
}

/**
 后序遍历:LRD 后序遍历左子树,后序遍历右子树,访问根节点
 
 @param tree 要遍历的树
 */
- (void)postorderTraversal:(TreeNode *)tree {
    if (tree) {
        [self postorderTraversal:tree.leftLeaf];
        [self postorderTraversal:tree.rightLeaf];
        NSLog(@"%@\n",tree.nodeName);
    }
}

/**
 层次遍历:按照从上到下、从左到右的次序进行遍历。先遍历完一层，再遍历下一层，因此又叫广度优先遍历。
 
 @param tree 要遍历的树
 */
- (void)levelTraversal:(TreeNode *)tree {
    if (tree) {
        NSMutableArray *nodeQueue = [[NSMutableArray alloc]initWithCapacity:0];
        [nodeQueue addObject:tree];
        while (nodeQueue.count) {
            TreeNode *node = nodeQueue.firstObject;
            NSLog(@"%@\n",node.nodeName);
            [nodeQueue removeObjectAtIndex:0];
            
            if (node.leftLeaf) {
                [nodeQueue addObject:node.leftLeaf];
            }
            if (node.rightLeaf) {
                [nodeQueue addObject:node.rightLeaf];
            }
        }
    }
}

/**
 二叉树深度：从根节点到叶子结点依次经过的结点形成树的一条路径，最长路径的长度就是树的深度。
 如果根节点为空，则深度为0；
 如果左右节点都是空，则深度为1；
 递归思想：二叉树的深度=max(左子树深度，右子树深度)+1;
 
 @param tree 要遍历的树
 */
- (NSInteger)depthTree:(TreeNode *)tree {
    if (!tree) {
        return 0;
    }
    if (!tree.leftLeaf && !tree.rightLeaf) {
        return 1;
    }
    NSInteger leftDepth  = [self depthTree:tree.leftLeaf];
    NSLog(@"leftDepth is %d",(int)leftDepth);
    NSInteger rightDepth = [self depthTree:tree.rightLeaf];
    NSLog(@"rightDepth is %d",(int)rightDepth);
    return MAX(leftDepth, rightDepth) + 1;
}

/**
 翻转二叉树:又叫求二叉树的镜像，就是把二叉树的左右子树对调。
 此算法是自底向上对调，也就是从叶子结点开始对调，依次向上进行。
 而且是，先对调完左子树，再对调右子树；
 注意：函数返回的始终是传入的结点。只不过可能是被交换了“左右孩子结点”的结点。
 @param tree 要翻转的tree
 */
- (TreeNode *)invertBinaryTree:(TreeNode *)tree {
    NSLog(@"tree.name %@",tree.nodeName);

    if (!tree) {
        return nil;
    }
    if (!tree.leftLeaf && !tree.rightLeaf) {
        return tree;
    }
   
   TreeNode *leftResultNode =  [self invertBinaryTree:tree.leftLeaf];
    NSLog(@"******************************** %@",leftResultNode.nodeName);
    
    TreeNode *rightResultNode = [self invertBinaryTree:tree.rightLeaf];
    NSLog(@"******************************** %@",rightResultNode.nodeName);

    // 当当前结点的左右孩子结点都没有“孩子结点”时，可以交换当前结点的“左右孩子结点”；
    NSLog(@"将要交换的tree %@ %@",tree.leftLeaf.nodeName, tree.rightLeaf.nodeName);
    TreeNode *tempNode = tree.leftLeaf;
    tree.leftLeaf = tree.rightLeaf;
    tree.rightLeaf = tempNode;

//    NSLog(@"交换后的tree %@",tree.nodeName);

    return tree;
}

@end

